This application is directed to similar subject matter as commonly assigned U.S. patent application Ser. Nos. 09/506,230 entitled “Apparatus and Method for Dispatching Fixed Priority Threads Using a Global Run Queue in a Multiple Run Queue System” and Ser. No. 09/506,856 entitled “Apparatus and Method for Starvation Load Balancing Using a Global Run Queue in a Multiple Run Queue System”, both filed on Feb. 17, 2000, and both hereby incorporated by reference in their entirety.
1. Technical Field
The invention is directed to apparatus and methods for periodic load balancing in a multiple run queue system.
2. Description of Related Art
Multiple processor systems are generally known in the art. In a multiple processor system, a process may be shared by a plurality of processors. The process is broken up into threads which may be processed concurrently. However, the threads must be queued for each of the processors of the multiple processor system before they may be executed by a processor.
One known technique for queuing threads to be dispatched by a processor in a multiple processor system is to maintain a single centralized queue, or “run queue.” As processors become available, they take the next thread in the queue and process it. The drawback to this approach is that the centralized queue becomes a bottleneck for the threads and processing time may be lost due to processors spinning on a run queue lock, i.e. becoming idle, while waiting to take the next thread from the centralized queue.
Another known technique for queuing threads is to maintain separate queues for each processor. Thus, when a thread is created, it is assigned to a processor in a round robin fashion. With such a technique, some processors may become overloaded while other processors are relatively idle. Furthermore, some low priority threads may become starved, i.e. are not provided with any processing time, because higher priority threads are added to the run queue of the processor for which the low priority threads are waiting.
Thus, there is a need for new technology to provide apparatus and methods for balancing the workload of a multiple processor system while maintaining a high throughput in the multiple processor system.